class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        storage={}
        def calsteps(val):
            if val==1:
                return 0
            try:
                step=storage[val]
                return step
            except KeyError:
                if val%2==0:
                    val//=2
                else:
                    val=3*val+1
                step=calsteps(val)
                storage[val]=step
                return 1+step
        raw=list(range(lo,hi+1))
        width=len(raw)
        steps=[calsteps(i) for i in raw]
        #print(steps)
        # if k<=width//2:
        #     offset=0
        #     while offset!=k+1:
        #         mini=offset
        #         for i in range(offset,width):
        #             if steps[i]<steps[mini]:
        #                 mini=i
        #             elif steps[i]==steps[mini] and raw[i]<raw[mini]:
        #                 mini=i
        #         temp=steps[offset]
        #         steps[offset]=steps[mini]
        #         steps[mini]=temp
        #         temp=raw[offset]
        #         raw[offset]=raw[mini]
        #         raw[mini]=temp
        #         offset+=1
        #     return raw[k-1]
        # else:
        #     offset=width-1
        #     while offset!=k-2:
        #         maxi=offset
        #         for i in range(0,offset+1):
        #             if steps[i]>steps[maxi]:
        #                 maxi=i
        #             elif steps[i]==steps[maxi] and raw[i]>raw[maxi]:
        #                 maxi=i
        #         temp=steps[offset]
        #         steps[offset]=steps[maxi]
        #         steps[maxi]=temp
        #         temp=raw[offset]
        #         raw[offset]=raw[maxi]
        #         raw[maxi]=temp
        #         offset-=1
        #     return raw[k-1]
        return sorted(range(lo,hi+1),key=lambda x:steps[x-lo])[k-1]

s=Solution()
print(s.getKth(7,11,4))


'''
执行用时：
296 ms
, 在所有 Python3 提交中击败了
64.86%
的用户
内存消耗：
24.3 MB
, 在所有 Python3 提交中击败了
20.97%
的用户
'''